class Solution
{
public:
    int findUnsortedSubarray(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> leftMax(n);
        vector<int> rightMin(n);
        leftMax[0] = nums[0];
        for (int i = 1; i < n; ++i)
        {
            leftMax[i] = max(nums[i], leftMax[i - 1]);
        }
        rightMin[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i)
        {
            rightMin[i] = min(nums[i], rightMin[i + 1]);
        }
        int left = -1;
        int right = n;
        if (nums[0] == rightMin[0])
        {
            left = 0;
            while (left < n - 1 && nums[left + 1] >= nums[left] && nums[left + 1] == rightMin[left + 1])
            {
                ++left;
            }
        }
        if (nums[n - 1] == leftMax[n - 1])
        {
            right = n - 1;
            while (right > 0 && nums[right] >= nums[right - 1] && nums[right - 1] == leftMax[right - 1])
            {
                --right;
            }
        }
        if (left >= right)
        {
            return 0;
        }
        return right - left - 1;
    }
};